NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c-part2/13809

Internet Message Format | 1996-08-05 | 1.9 KB

Path: mail2news.demon.co.uk!genesis.demon.co.uk
From: Lawrence Kirby <[e-mail]>
Newsgroups: comp.lang.c
Subject: Re: C compilers which optimize tail calls (was: GOTO controversy)
Date: Wed, 10 Apr 96 11:39:30 GMT
Organization: none
Message-ID: <[e-mail]>
References: <[e-mail]> <[e-mail]> <[e-mail]> <4keb44$[e-mail]>
Reply-To: [e-mail]
X-NNTP-Posting-Host: genesis.demon.co.uk
X-Newsreader: Demon Internet Simple News v1.27
X-Mail2News-Path: genesis.demon.co.uk

In article <4keb44$[e-mail]>
           [e-mail] "William D Clinger" writes:

>Stack allocation of mutable variables and data often
>interferes with proper tail recursion.  Consider
>
>int f (int n) {
>    int A[10];
>    int i;
>    for (i = 0; i < 10; i = i + 1)

It is more natural to write i = i + 1 as ++i or i++ in C.

>        A[i] = n * i;
>    return g (&n, &(A[0]));
>}
>
>Yes, it is possible to write a correct C compiler that
>compiles the tail-recursive call to g as a tail recursion.

What tail recursion? There's no recursion there at all. With tail recursion
the function is calling itself before returning so the local variables
between invocations are somewhat compatible. There was a case of mutual
recursion posted earlier. This is trickier to deal with but could be reduced
to simple recursion with appropriate function inlining (although the scope
of that is realistically limited to fairly simple cases).

>I very much doubt whether any production C compiler
>can be relied upon to generate properly tail recursive code.

Many do for cases of simple (i.e. involving a single function) tail recursion
but it still remains that portable C code can't depend on it.

--
-----------------------------------------
Lawrence Kirby | [e-mail]
Wilts, England | [e-mail]
-----------------------------------------